// 欧拉函数：1~n中与n互质的个数
// N(1-1/p0)*(1-1/pi);
// 和分解质因数的时间复杂度一样：sqrt(n)

#include <iostream>
typedef long long LL;
using namespace std;

int main()
{
    int n;
    cin >> n;
    while (n--)
    {
        int a;
        cin >> a;
        LL ret = a;
        for (int i = 2; i <= a / i; ++i)
        {
            if (a % i == 0)
            {
                ret = ret * (i - 1) / i;
                while (a % i == 0)
                    a /= i;
            }
        }
        // 如果a不是1， 那么还要将a本身乘上
        if (a != 1)
            ret = ret * (a - 1) / a;
        cout << ret << endl;
    }
    return 0;
}